/**
 * Copyright (c) 2009-2011, chunquedong(YangJiandong)
 * 
 * This file is part of ChunMap project
 * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE(Version >=3)
 * 
 * History:
 *     2010-05-05  Jed Young  Creation
 */
package chunmap.model.algorithm;

import java.util.ArrayList;
import java.util.List;

import chunmap.model.coord.Position;
import chunmap.model.elem.Envelope;
import chunmap.model.elem.LineSegment;
import chunmap.model.elem.PointLineBag;
import chunmap.model.geom.GeoPoint;
import chunmap.model.geom.Geometry;
import chunmap.model.geom.LineString;
import chunmap.util.MyAssert;

/**
 * 单调链
 * 
 * @author chunquedong
 * 
 */
public class MonotonyChain {

	private final List<Position> points = new ArrayList<Position>();
	private int cursor;

	public Position getFirst() {
		return points.get(0);
	}

	public Position getLast() {
		return points.get(points.size() - 1);
	}

	public int size() {
		return points.size();
	}

	public Position get(int i) {
		return points.get(i);
	}

	protected int getCursor() {
		return cursor;
	}

	protected void resetCursor() {
		cursor = 0;
	}

	protected Position getCursorPoint() {
		return points.get(cursor);
	}

	protected void increaseCursor() {
		cursor++;
	}

	protected void reduceCursor() {
		cursor--;
	}

	protected boolean hasPre() {
		return cursor > 0;
	}

	protected Position getPrePoint() {
		return this.get(cursor - 1);
	}

	protected LineSegment getPreLineSegment() {
		return new LineSegment(get(cursor - 1), get(cursor));
	}

	protected boolean hasNext() {
		return cursor < this.size() - 1;
	}

	protected Position getNextPoint() {
		return this.get(cursor + 1);
	}

	protected LineSegment getNextLineSegment() {
		return new LineSegment(get(cursor), get(cursor + 1));
	}

	/**
	 * 追加到最大的位置
	 * 
	 * @param p
	 * @return
	 */
	public boolean add(Position p) {
		if (size() == 0) {
			points.add(p);
			return true;
		} else if (p.getX() >= getLast().getX()) {
			points.add(p);
			return true;
		}
		return false;
	}

	/**
	 * 插入到最小的位置
	 * 
	 * @param p
	 * @return
	 */
	public boolean insert(Position p) {
		if (size() == 0) {
			points.add(p);
			return true;
		} else if (p.getX() <= getFirst().getX()) {
			points.add(0, p);
			return true;
		}
		return false;
	}

	public boolean join(MonotonyChain other) {
		Position p1 = this.getLast();
		Position p2 = other.getFirst();
		if (p1.getX() >= p2.getX()) {
			points.addAll(other.points);
			return true;
		}
		return false;
	}

	public LineString toLineString() {
		return new LineString(points);
	}

	public Envelope getEnvelop() {
		double minY;
		double maxY;
		minY = maxY = getFirst().getY();
		for (Position p : points) {
			double y = p.getY();
			if (y < minY) {
				minY = y;
			} else if (y > maxY) {
				maxY = y;
			}
		}
		return new Envelope(getFirst().getX(), minY, getLast().getX(), maxY);
	}

	private void setStartCursor(MonotonyChain other) {
		resetCursor();
		if (this.getCursorPoint().getX() >= other.getCursorPoint().getX()) {
			return;
		}
		double minX = other.getCursorPoint().getX();
		while (getCursorPoint().getX() < minX && this.hasNext()) {
			this.increaseCursor();
		}

		if (this.hasPre())
			this.reduceCursor();
	}

	private int compareY(MonotonyChain other) {
		return Double.compare(this.getCursorPoint().getY(), other
				.getCursorPoint().getY());
	}

	public PointLineBag intersection(MonotonyChain other)
    {
        PointLineBag geometrys=new PointLineBag();
        intersectionSub(other, geometrys, true);
        return geometrys;
    }
    public boolean hasIntersection(MonotonyChain other)
    {
        PointLineBag geometrys=new PointLineBag();
        return intersectionSub(other, geometrys, false);
    }

    private boolean intersectionSub(MonotonyChain other, PointLineBag geometrys, boolean myContinue)
    {
        //geometrys = new PointLineBag();
        // 空的
        if (this.size() == 0 || other.size() == 0)
            return false;
        // 没有交集
        if (!this.getEnvelop().hasIntersect(other.getEnvelop()))
        {
            return false;
        }

        // 初始化
        this.setStartCursor(other);
        other.setStartCursor(this);
        // 纵坐标大小比较
        int compare = compareY(other);
        
        boolean mustHasIntersection = false;
        // 交集运算
        while (true)
        {
            int nowCompare = compareY(other);
            if (mustHasIntersection || (nowCompare == 0 || nowCompare != compare))
            {// 位置改变时必有交点
                Geometry g = getIntersection(other);
                if (g != null)
                {
                    geometrys.add(g);
                    if (!myContinue)
                    {
                        return true;
                    }
                    compare = nowCompare;
                    mustHasIntersection = false;
                }
                else
                {
                	mustHasIntersection = true;
                }
            }
            // 增长
            if (!increase(other))
                break;
        }
        return geometrys.size()>0;
    }

	// 向前增长
	private boolean increase(MonotonyChain other) {
		if (this.getCursorPoint().getX() < other.getCursorPoint().getX()) {
			if (this.hasNext())
				this.increaseCursor();
			else
				return false;
		} else if (this.getCursorPoint().getX() > other.getCursorPoint().getX()) {
			if (other.hasNext())
				other.increaseCursor();
			else
				return false;
		} else {
			if (this.hasNext())
				this.increaseCursor();
			else if (other.hasNext())
				other.increaseCursor();
			else
				return false;
		}
		return true;
	}

	// 从游标位置前的交集
	private Geometry getIntersection(MonotonyChain other) {
		if (hasPre()) {
			return other.getIntersection(getPreLineSegment());
		} else {
			return other.getIntersection(this.getCursorPoint());
		}
	}

	// 游标位置前和线段的交集
	private Geometry getIntersection(LineSegment ls) {
		if (hasPre()) {
			Object r = getPreLineSegment().intersection(ls);
            if (r == null) return null;

            if (r instanceof Position)
            {
                return new GeoPoint((Position)r);
            }
            else if (r instanceof Position[])
            {
                return new LineString((Position[])r);
            }
            else
            {
                throw new MyAssert.AssertionEexception("unreachable code");
            }
		} else {
			return getIntersection(ls, this.getCursorPoint());
		}
	}

	// 游标位置前和点 的交集
	private Geometry getIntersection(Position p) {
		if (hasPre()) {
			return getIntersection(getPreLineSegment(), p);
		} else {
			if (p.equals(this.getCursorPoint()))
				return new GeoPoint(p);
			else
				return null;
		}
	}

	private Geometry getIntersection(LineSegment ls, Position p) {
		if (ls.onLineSegment(p))
			return new GeoPoint(p);
		else
			return null;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((points == null) ? 0 : points.hashCode());
		return result;
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		MonotonyChain other = (MonotonyChain) obj;
		if (points == null) {
			if (other.points != null)
				return false;
		} else if (!points.equals(other.points))
			return false;
		return true;
	}

	@Override
	public String toString() {
		return "MonotonyChain [" + points + "]";
	}

}